package seqlist;

import seqlist.oj.ListNode;

import java.security.PrivateKey;
//车厢类
class  DoubleNode{
    DoubleNode prev;
    int  val;
    DoubleNode next;

    public DoubleNode(int val) {
        this.val = val;
    }
}
       /**
        * 基于int的双向链表
        */
public class DoubleLinkedList {
           private int size;
           private DoubleNode first;
           private DoubleNode last;

           //头插法
           public void addFirst(int val) {
               DoubleNode f = first;
               DoubleNode node = new DoubleNode(val);
               first = node;
               if (f == null) {
                   last = node;
               } else {
                   node.next = f;
                   f.prev = node;

               }
               size++;
           }

           public void addLast(int val){
               DoubleNode l=last;
               DoubleNode node =new DoubleNode(val);
               last=node;
               if(l==null){
                   //链表为空
                  first=node;
               }else{
                   node.prev=l;
                   l.next=node;
               }
           size++;
           }

           public void addIndex(int index,int val){
               if(index<0 || index>size){
                   System.err.println(" add index  illegal");
               }
               if(index==0){
                   addFirst(val);
               }
               else if(index==size){
                   addLast(val);
               }else{
                   DoubleNode node=node(index);
                   //此时node就是index对应的结点
                   DoubleNode prev=node.prev;
                   DoubleNode NewNode=new DoubleNode(val);
                   NewNode.next=node;
                   node.prev=NewNode;
                   prev.next=NewNode;
                   NewNode.prev=prev;
               }
             size++;
           }


           public int get(int index) {
               if (rangeCheck(index)) {
                   DoubleNode node = node(index);
                   return node.val;
               }else{
                   System.err.println("get index illegal");
                   return -1;
               }
           }
           public boolean contains(int val){
               DoubleNode node=first;
               while(node!=null) {
                   if (node.val == val) {
                       return true;
                   } else {
                       node=node.next;
                   }
               }
               return false;
           }

           public void set(int index, int newVal){
               if(rangeCheck(index)){
                   DoubleNode node=node(index);
                   node.val=newVal;
               }else{
                   System.err.println("set index illegal");
               }
           }
           public void removeOnce(int val){
               for(DoubleNode x=first; x!=null;x=x.next){
                   if(x.val==val){
                       unLinked(x);
                       return;
                   }
               }
           }

           public void removeAll(int val){
               for(DoubleNode x=first; x!=null;x=x.next){
                   if(x.val==val){
                       DoubleNode next=x.next;
                       unLinked(x);
                       x=next;
                   }else{
                       x=x.next;
                   }
               }
           }

           //删除双向链表中的出现一次的元素
           private void  unLinked(DoubleNode node){
             DoubleNode prev=node.prev;
             DoubleNode next=node.next;
             if(prev==null){
                 first=next;
             }else {
                 prev.next = next;
                 node.prev = null;
             }
             if(last==null){
                 last=prev;
             }else{
                 next.prev = prev;
                 node.next = null;
             }
             size--;
           }


          private DoubleNode node(int index){
               if(index < size>>2){
                   DoubleNode node=first;
                   for (int i = 0; i < index; i++) {
                       node=node.next;
                   }
                   return node;
               }else{
                   DoubleNode node=last;
                   for (int i = size-1; i > index; i--) {
                       node=node.prev;
                   }
                   return  node;
               }
           }

           private boolean rangeCheck(int index){
               if(index<0 || index>=size){
                   return false;
               }else{
                   return true;
               }
           }

           public String toString() {
               String ret = "";
               DoubleNode node = first;
               while (node != null) {
                   ret += node.val + "->";
                   node = node.next;
               }
               ret += "NULL";
               return ret;
           }

           public static void main(String[] args) {
               DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
               doubleLinkedList.addFirst(1);
               doubleLinkedList.addFirst(2);
               doubleLinkedList.addFirst(3);
               doubleLinkedList.addLast(4);
               doubleLinkedList.addIndex(2,3);
               System.out.println(doubleLinkedList);
//               System.out.println(doubleLinkedList.get(2));
//               doubleLinkedList.set(2,5);
//               System.out.println(doubleLinkedList);
//               System.out.println(doubleLinkedList.contains(1));
//               System.out.println(doubleLinkedList.contains(9));
 //              doubleLinkedList.removeOnce(2);
               doubleLinkedList.removeAll(3);
               System.out.println(doubleLinkedList);

           }
       }
